/******************************************************************************
 * @file   :  item9.cpp
 * @brief  :  Choose carefully among erasing options
 * Created :  09/11/2010 09:57:41 AM
 * Revision:  none
 * Compiler:  gcc -Wall -Wextra item9.cpp
 *
 * @author :  coanor, coanor@gmail.com
 ******************************************************************************/
#include <string>
#include <vector>
#include <deque>

#include <list>

#include <map>

#include <fstream>		/* for ofstream */
#include <algorithm>	/* for remove_if */

using namespace std;

int bad_map_value(pair<int, int> elem)
{
	return 0;
}

int bad_vec_value(int x)
{
	return 0;
}

int main()
{
	string str;
	vector<int> vec;
	deque<int> deq;

	/* If you have a contiguous-memory container(vector, deque or string),
	 * the best way to erase-remove idiom is:
	 */
	str.erase(remove(str.begin(), str.end(), 1963), str.end());
	vec.erase(remove(vec.begin(), vec.end(), 1963), vec.end());
	deq.erase(remove(deq.begin(), deq.end(), 1963), deq.end());

	/* the remove member function is the best way to get rid of element
	 * with a specific value when c is a list
	 */
	list<int> lst;
	lst.remove(1963);

	/* For vector, string, deque and list, we can use predicate bad_value */
	vec.erase(remove_if(vec.begin(), vec.end(), bad_vec_value), vec.end());

	/* This is the best way to get rid of objects where bad_value returns
	 * true when used in list
	 */
	lst.remove_if(bad_vec_value);

	/* When standard associative container(i.e.. a set, multiset, map
	 * or multimap), the use of anything named remove is COMPLETELY
	 * wrong, such containers have no member function named remove.
	 *
	 * The proper way to approach the problem is to call erase, not only
	 * does this do the right thing, it does it efficiently, taking logarithmic
	 * time.(The remove-based techniques for sequence containers require
	 * linear time.)Furthermore, the assiciative container erase function
	 * has the advantage of being based on EQUIVALENCE instead of EQUALITY.
	 */
	map<int, int> i_s;
	i_s.erase(i_s.find(1963));

	/* For the standard assiciative containers, it's not quite so straightforward.
	 * There are two ways to approach the problem, one uses remove_copy_if to copy
	 * the values we want into a new container, then swap the contents of the original
	 * container with those of the new one. The drawback to this approach is
	 * that it involves copying all the elements that aren't being removed,and
	 * such copying might cost us more than we're intereseted in paying.
	 */
	map<int, int> good_value;	/* temporary container to hold unremoved values */
	remove_copy_if(i_s.begin(),
	               i_s.end(),
				   inserter(good_value, good_value.end()),
				   bad_map_value);
	i_s.swap(good_value);

	/* The second way is simple! Because the value of exression i++ is it's old
	 * value, but as a side effect, i is incremented, hence we pass i's old (unincremented)
	 * value to erase, but we also increment i itself before erase begins executing.
	 * That exactly what we eant.
	 */
	for (map<int, int>::iterator i = i_s.begin();
			i != i_s.end();
			/* do nothing */) {
		if (bad_map_value(*i)) {
			/* Pass the current i to erase and increment i as 
			 * a side effect, for good values, just increment!
			 */
			i_s.erase(i++);
		}
		else {
			++i;
		}
	}

	ofstream log_file;
	for (map<int, int>::iterator i = i_s.begin();
	i != i_s.end();) {
		if (bad_map_value(*i)) {
			log_file << "erasing" << i->first << "\n";
			i_s.erase(i++);
		}
		else {
			++i;
		}
	}
	
	/* We must take a different tack with vector, string and deque, in particular,
	 * we must take advantage of erase's return value. That return value is exactly
	 * what we need: it's a valid iterator pointing to the element following the 
	 * erased element once the erase has been accomplished.
	 *
	 * This works wonderfully, but only for the standard sequence containers, due
	 * to resoning one might question, erase's return type for the standard associative
	 * container is void, for those containers, you have to use the postincrement-the-
	 * iterator-you-pass-to-erase technique.(Incidently, this kind of difference between
	 * coding for sequence containers and associative containers is an example of 
	 * why it is generally ill-advised to try to write container-indipendent code)
	 */
	for (vector<int>::iterator i = vec.begin(); i != vec.end();) {
		if (bad_vec_value(*i)) {
			log_file << "Erasing " << *i << '\n';
			i = vec.erase(i);	// Keep i valid by assigning erase's
		}	                    // return value to it.
		else {
			++i;
		}
	}

	/******************************* CONCLUSION ***********************************
	 * 1) To eliminate all objects in a container that have a particular value:
	 *    If the container is a vector,string,or deque, use the erase-remove idiom.
	 *
	 *    If the container is a list, use list::remove.
	 *
	 *    If the container is a standard associative container, use its erase member function.
	 *
	 * 2) To eliminate all objects in a container that satisfy a particular predicate:
	 *    If the container is a vector, string, or deque, use the erase-remove_if idiom.
	 *
	 *    If the container is a list, use list::remove_if.
	 *
	 *    If the container is a standard associative container, use remove_copy_if and swap,
	 *    or write a loop to walk the container elements, being sure to postincrement your
	 *    iterator when you pass it to erase.
	 *
	 * 3) To do something inside the loop(in addition to erasing objects):
	 *    If the container is a standard sequence container, write a loop to walk the
	 *    container elements, being sure to update your iterator with erase's return
	 *    value each time von call it.
	 *
	 *    If the container is a standard associative container, write a loop to walk the
	 *    container elements, being sure to postincrement your iterator when you pass it
	 *    to erase.
	 *
	 *    XXX: How about the list? It turns out that for purposes of iterating and
	 *    erasing, you can treat it like a vector/string/deque or you can treat it
	 *    like an associative container. Both approaches work for list. The convertion
	 *    it to work with list in the same way as vector, string, and deque, because
	 *    these are all sequence containers. Experienced STL hands would find it odd
	 *    to come across list code that iterates and erases using the associative
	 *    container technique.
	 *****************************************************************************/
	return 0;
}
